package com.tgy.tree;

import com.tgy.util.printer.BinaryTreeInfo;
import lombok.Getter;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2020/9/14 9:14 下午
 */
public class BinaryTree<E> implements BinaryTreeInfo {

  protected int size;

  @Getter
  protected Node<E> root;

  public BinaryTree() {

  }

  public static class Node<E> {

    E element;

    Node<E> parent;

    Node<E> left;

    Node<E> right;

    public Node(E element, Node<E> parent) {
      this.element = element;
      this.parent = parent;
    }

    public boolean isLeaf() {

      return left == null && right == null;
    }

    /**
     * 当前节点是父节点的左节点
     * @return
     */
    protected boolean isLeftNode() {

      return parent !=null && this.equals(parent.left);
    }

    /**
     * 当前节点是父节点的右节点
     * @return
     */
    protected boolean isRightNode() {

      return parent != null && this.equals(parent.right);
    }

    public int degree() {

      if (left == null && right == null) {

        return 0;
      }else if (left != null && right != null){

        return 2;
      }else {

        return 1;
      }

    }
  }

  /**
   * 元素的数量
   * @return
   */
  public int size(){
    return size;
  }

  /**
   * 是否为空
   * @return
   */
  public boolean isEmpty(){

    return size == 0;
  }

  /**
   * 清空所有元素
   */
  public void clear() {

    root = null;
    size = 0;
  }

  public boolean contains(E element) {

    Node<E> eNode = inorderTaversalTree(element);

    return eNode != null;
  }

  /**
   * 层序遍历
   * @return
   */
  public String levelTraversalTree() {


    if (root == null) {

      return "";
    }

    StringBuilder sb = new StringBuilder();

    LinkedList<Node<E>> nodeQueue = new LinkedList<>();

    nodeQueue.offer(root);

    int levelInQueueSize = 1;
    Node<E> node = root;

    while (!nodeQueue.isEmpty()) {

      node = nodeQueue.poll();

      levelInQueueSize--;


      if (node.left != null) {

        nodeQueue.offer(node.left);
      }

      if (node.right != null) {

        nodeQueue.offer(node.right);
      }

      sb.append(node.element);
      if (levelInQueueSize == 0) {

        levelInQueueSize = nodeQueue.size();
        sb.append("\n");
      }else {

        sb.append(",");
      }
    }

    return sb.toString();
  }

  /**
   * 后续遍历树
   */
  public String postinderTraversalTree() {

    if (root == null) {

      return "";
    }

    StringBuilder sb = new StringBuilder();

    Stack<Node<E>> nodeStack = new Stack<>();


    Node<E> node = root;

    Node<E> preNode = null;

    while (node != null || !nodeStack.isEmpty()) {

      while (node != null) {

        nodeStack.push(node);

        if (node.right != null) {

          nodeStack.push(node.right);
        }

        node = node.left;
      }

      Node<E> tmpNode = nodeStack.pop();

      if (tmpNode.isLeaf() || ( preNode !=null && preNode.parent == tmpNode) ) {

        sb.append(tmpNode.element).append(",");
        preNode = tmpNode;

      }else {

        node = tmpNode;
      }
    }

    return sb.toString();
  }


  /**
   * 中序遍历
   * @param
   */
  protected Node<E> inorderTaversalTree(E element) {

    if (root == null) {

      return null;
    }

    Stack<Node<E>> nodeStack = new Stack<>();

    Node<E> node = root;

    while (node!= null || !nodeStack.isEmpty()) {

      while (node != null) {

        nodeStack.push(node);

        node = node.left;
      }

      node = nodeStack.pop();
      if (node.element.equals(element)) {

        return node;
      }
      node = node.right;
    }

    return null;
  }

  /**
   * 交换左右子树
   */
  public void invertBinaryTree() {

    if (root == null) {

      return;
    }

    LinkedList<Node<E>> nodeQueue = new LinkedList<>();

    Node<E> node = root;

    while (node != null || !nodeQueue.isEmpty()) {

      if (node.left != null) {

        nodeQueue.offer(node.left);
      }

      if (node.right != null) {

        nodeQueue.offer(node.right);
      }

      Node<E> tmpNode = node.left;
      node.left = node.right;
      node.right = tmpNode;

      node = nodeQueue.poll();
    }

  }



  public Integer treeHeight() {

    return recursionTreeHeight(root,0);
  }


  /**
   * 打印二叉树的树状结构
   * @return
   */
  public String printTree() {

    int height = treeHeight();

    if (height == 0) {
      return "";
    }

    long allWidth = (long) Math.pow(2,height);
    StringBuilder sb = new StringBuilder();

    LinkedList<Node<E>> nodeQueue = new LinkedList<>();

    Node<E> node = root;

    int elementInQueueNum = 1;
    nodeQueue.offer(node);

    int currentheight = 0;


    while (!nodeQueue.isEmpty()) {


      node = nodeQueue.poll();
      if (currentheight < height) {

        sb.append(node == null?"null":node.element).append(",");
      }
      elementInQueueNum--;

      if (node != null) {

        nodeQueue.offer(node.left);
        nodeQueue.offer(node.right);
      }


      if (elementInQueueNum == 0) {

        currentheight++;

        elementInQueueNum = nodeQueue.size();

        if (sb.charAt(sb.length() -1) == ',') {

          sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("\n");
      }

    }

    return sb.toString();
  }



  /**
   * 查找后继节点
   * @param node
   * @return
   */
  public Node<E> successorNode(Node<E> node) {


    if (node == null) {

      return null;
    }

    if (node.right != null) {
      //往下找
      node = node.right;
      while (node != null && node.left != null) {

        node = node.left;
      }

      return node;
    }else {
      //往上找
      while (node.parent != null && node.parent.right == node) {

        node = node.parent;
      }

      return node.parent;
    }
  }

  /**
   * 中序递归遍历
   * @param visitor
   */
  public void inorderRecursionTraversal(Visitor<E> visitor) {

    doInorderRecursionTraversal(root,visitor);
  }

  private void doInorderRecursionTraversal(Node<E> node,Visitor<E> visitor) {

    if (node == null || visitor.stop) {

      return;
    }

    doInorderRecursionTraversal(node.left,visitor);

    if (visitor.stop){
      return;
    }
    visitor.visit(node.element);

    doInorderRecursionTraversal(node.right,visitor);
  }

  /**
   * 前驱节点
   * @param node
   * @return
   */
  public Node<E> precursorNode(Node<E> node) {

    if (node == null) {

      return node;
    }

    if (node.left != null) {

      node  = node.left;
      while (node != null && node.right != null ) {

        node = node.right;
      }
      return node;

    }else {


      while (node.parent != null && node.equals(node.parent.left)) {

        node = node.parent;
      }

      return node.parent;
    }

  }

  private Integer recursionTreeHeight(Node<E> node,int height) {


    if (node == null) {

      return height;
    }

    return Math.max(recursionTreeHeight(node.left,height + 1),recursionTreeHeight(node.right,height+1));

  }


  private void printer(Node<E> node,StringBuilder sb) {

    if (node == null) {

      return;
    }

    printer(node.left,sb);
    levelPrinter(node,sb);
    sb.append(node.element).append(",");
    printer(node.right,sb);
  }

  /**
   * 层序遍历
   * @param node 根节点
   * @param sb   组装的字符串容器
   */
  protected void levelPrinter(Node<E> node, StringBuilder sb) {

    if (node == null || sb == null) {
      return;
    }

    LinkedList<Node<E>> queue = new LinkedList<>();

    int everylevelNum = 1,treeHeight = 0;
    queue.offer(node);

    while (!queue.isEmpty()) {

      Node<E> topNode = queue.poll();

      everylevelNum--;

      if (topNode.left != null) {

        queue.offer(topNode.left);
      }

      if (topNode.right != null) {

        queue.offer(topNode.right);
      }

      /**
       * 当 everyLevelNum = 0 时正好是当前层最后一个节点出队列。queue里面装的正好是下一层的所有节点。
       */
      if (everylevelNum == 0) {

        treeHeight++;
        //  获取下一层节点数
        everylevelNum = queue.size();
      }

      sb.append(topNode.element).append(",");
    }


    sb.append(" tree height ").append(treeHeight).append(",");
  }



  /**
   * 中序非递归遍历tree
   * @param node
   * @param sb
   */
  private void inorderTraversalTree(Node<E> node,StringBuilder sb) {

    if (node == null || sb == null) {
      return;
    }

    Stack<Node<E>> stack = new Stack<>();

    while (true) {

      while (node != null) {

        stack.push(node);
        node = node.left;
      }

      //  node.left 为 null, 这里取值要保证stack非空

      if (stack.isEmpty()) {

        return;
      }

      node = stack.pop();
      sb.append(node.element).append(",");
      node = node.right;

    }

  }

  /**
   * 前序遍历
   * @param node
   * @param sb
   */
  private void preorderTraversalTree(Node<E> node, StringBuilder sb) {

    if (node == null || sb == null) {

      return;
    }

    Stack<Node<E>> stack = new Stack<>();

    while (true) {

      while (node != null) {

//                把节点保存起来，为了拿到保存节点的right节点
        stack.push(node);
        sb.append(node.element).append(",");
        node = node.left;
      }

      if (stack.isEmpty()) {

        return;
      }

      node = stack.pop().right;
    }
  }

  /**
   * 后序遍历
   * @param node
   * @param sb
   */
  private void postorderTraversalTree(Node<E> node, StringBuilder sb) {

    if (node == null || sb == null) {

      return;
    }

    Stack<Node<E>> stack = new Stack<>();

    Node<E> lastVistNode = null;

    while (true) {

      while (node != null) {

        stack.push(node);

        if (node.right != null) {

          stack.push(node.right);
        }

        node = node.left;
      }

      if (stack.isEmpty()) {

        break;
      }

      Node<E> topNode = stack.pop();

      if (topNode.isLeaf() || (lastVistNode != null && lastVistNode.parent == topNode)) {

        sb.append(topNode.element).append(",");
        lastVistNode = topNode;

      } else {

        node = topNode;
      }
    }

  }

  /**
   * 当前二叉树是否是完全二叉树
   * @return
   */
  public boolean isCompleteBinaryTree() {

    if (root == null) {

      return false;
    }

    LinkedList<Node<E>> nodeQueue = new LinkedList<>();


    Node<E> node = root;

    boolean nextMustLeaf = false;

    while (node != null || !nodeQueue.isEmpty()) {

      if (nextMustLeaf && !node.isLeaf()) {

        return false;
      }

      if (node.left != null) {

        nodeQueue.offer(node.left);
      }else if (node.right != null) {

        return false;
      }

      if (node.right != null) {

        nodeQueue.offer(node.right);
      }else {

//                完全二叉树从节点度为1或者0开始之后的节点必须是叶子节点
        if (!nextMustLeaf) {
          nextMustLeaf = true;
        }
      }

      // 进行操作
      node = nodeQueue.poll();
    }

    return true;
  }

  /**
   * 中树遍历的下一个元素
   * @param node
   * @return
   */
  protected Node<E> nextNode(Node<E> node) {

    if (node == null) {

      return null;
    }

    if (node.right != null) {

//            往下找
      node = node.right;

      while (node != null && node.left != null) {

        node = node.left;
      }

      return node;

    }else {

//            往上找
      while (node != null && node.parent != null) {

        if (node.equals(node.parent.right)) {

          node = node.parent;
        }else {

          break;
        }
      }

      return node.parent;
    }

  }



  @Override
  public Object root() {

    return root;
  }

  @Override
  public Object left(Object node) {

    return ((Node<E>) node).left;
  }

  @Override
  public Object right(Object node) {

    return ((Node<E>) node).right;
  }

  @Override
  public Object string(Object node) {

    return ((Node<E>) node).toString();
  }
}
